package DFS;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Classname JZ38全排列
 * @Description TODO
 * @Date 2022/12/10 14:46
 * @Created by xjl
 */
public class JZ38全排列 {

    public String[] permutation(String s) {
        ArrayList<String> lists=new ArrayList<>();
        char[] chars = s.toCharArray();
        StringBuilder sb=new StringBuilder();
        boolean[] visit=new boolean[s.length()];
        Arrays.sort(chars);
        dfs(chars,0,sb,lists,visit);
        String[] res=new String[lists.size()];
        for (int i=0;i<lists.size();i++){
            res[i]=lists.get(i);
        }
        return res;
    }

        /**
         * @description 回溯算法的固定格式 ： 目标字符target    visit[]
          * @param: chars
         * @param: index
         * @param: sb
         * @param: lists
         * @param: visit
         * @date: 2022/12/10 15:05
         * @return: void
         * @author: xjl
        */
    private void dfs(char[] chars, int index, StringBuilder sb, ArrayList<String> lists, boolean[] visit) {
        if (index==chars.length){
            lists.add(sb.toString());
            return;
        }
        for (int i=0;i<chars.length;i++){
            // 如果是数据有相同的 将会跳过
            if (visit[i] || (i > 0 && !visit[i - 1] && chars[i - 1] == chars[i])) {
                continue;
            }
            visit[i]=true;
            sb.append(chars[i]);
            dfs(chars,index+1,sb,lists,visit);
            sb.deleteCharAt(sb.length()-1);
            visit[i]=false;
        }
    }
}
